package com.yq.leetcodeOld;

import java.util.Arrays;

/**
 * @ClassName Solution31
 * @Description TODO
 * @Author yaoqiang
 * @Date 2022/3/7 9:36
 * @Version 1.0
 */
public class Solution31 {
    public static void main(String[] args) {

        int[] nums = new int[]{1,2,3};
        nextPermutation(nums);


    }
    public static void nextPermutation(int[] nums){
        int n=nums.length; //数组最大长度
        if (n<2)    return; //特例
        int min=n-1; //较大值的最小值下标初始化为n-1
        boolean flag=false;//用于判断是不是递减序列
        for (int i=n-1;i>0;i--){
            if (nums[i]>nums[i-1]){ //从后往前遍历，遇到更小的数就开始下一步
                while (nums[i-1]>=nums[min]){
                    min--;
                }
                change(nums,i-1,min);//先交换，交换之后索引大于i-1的元素一定是降序的
                reverse(nums,i);//反转 从i开始
                flag=true;
                break;
            }
        }
    }


    public static void nextPermutation2(int[] nums) {
        int n = nums.length;
        if (n < 2) return; //特判
        int min = n - 1; //较大值中的最小值的下标初始化为n-1
        boolean flag = false; //用于判断是不是递减序列
        for (int i = n - 1; i > 0; i--) {
            if (nums[i] > nums[i - 1]) { //从后往前遍历，遇到更小数就开始下一步
                while (nums[i - 1] >= nums[min]) {//while循环用于找到较大数中的最小数所在的索引min
                    min--;
                }
                change(nums, i - 1, min);//先交换，交换之后索引大于i-1的元素一定是降序的。
                reverse(nums, i);//再反转（从i开始）
                flag = true;//有交换就不是递减数组
                break;
            }
        }
        if (!flag) Arrays.sort(nums); //flag没变说明是递减数组，那就递增排nums
        System.out.println(Arrays.toString(nums));
    }

    //交换位置i和j的值
    public static void change(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

    //反转nums中start位置到最后部分
    public static void reverse(int[] nums, int start) {
        int n = nums.length;
        int end = n - 1;
        while (end > start) {
            change(nums, start, end);
            end--;
            start++;
        }
    }
}
